package com.zs.letcode.illustration_of_algorithm;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 剑指 Offer 27. 二叉树的镜像
 * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
 * <p>
 * 例如输入：
 * <p>
 * 4
 * /  \
 * 2   7
 * / \  / \
 * 1  3 6  9
 * 镜像输出：
 * <p>
 * 4
 * /  \
 * 7   2
 * / \  / \
 * 9  6 3 1
 * <p>
 *
 * <p>
 * 示例 1：
 * <p>
 * 输入：root = [4,2,7,1,3,6,9]
 * 输出：[4,7,2,9,6,3,1]
 *
 * <p>
 * 限制：
 * <p>
 * 0 <= 节点个数 <= 1000
 * <p>
 * 注意：本题与主站 226 题相同：https://leetcode-cn.com/problems/invert-binary-tree/
 * <p>
 * 相关标签
 * 树
 * 深度优先搜索
 * 广度优先搜索
 * 二叉树
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：Krahets
 * 链接：https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/59zt5i/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/8/16 11:57
 */
public class Chapter25 {
    public static void main(String[] args) {

    }

    /**
     * Definition for a binary tree node.
     */
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private class Solution {
        /**
         * 方法一：递归法 DFS
         *
         * @param root
         * @return
         */
        public TreeNode mirrorTree(TreeNode root) {
            if (root == null) {
                return null;
            }
            TreeNode tmp = root.left;
            root.left = mirrorTree(root.right);
            root.right = mirrorTree(tmp);
            return root;
        }

        /**
         * 方法二：辅助栈（或队列）
         */
        public TreeNode mirrorTree1(TreeNode root) {
            if (root == null) {
                return null;
            }
            Deque<TreeNode> stack = new LinkedList<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                if (node.left != null) stack.add(node.left);
                if (node.right != null) stack.add(node.right);
                TreeNode tmp = node.left;
                node.left = node.right;
                node.right = tmp;
            }
            return root;
        }
    }
}
